//面试题 17.23 最大黑方阵
//给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。 
//
// 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 
//最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。 
//
// 示例 1: 
//
// 输入:
//[
//   [1,0,1],
//   [0,0,1],
//   [0,0,1]
//]
//输出: [1,0,2]
//解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
// 
//
// 示例 2: 
//
// 输入:
//[
//   [0,1,1],
//   [1,0,1],
//   [1,1,0]
//]
//输出: [0,0,1]
// 
//
// 提示： 
//
// 
// matrix.length == matrix[0].length <= 200 
// 
// Related Topics 动态规划


package leetcode.editor.cn;

/**
 * 两个方向的前缀和+判断条件是阔以哒，但效率不知道怎么样
 */
class A面试题1723MaxBlackSquareLcci {
    public static void main(String[] args) {
        Solution solution = new A面试题1723MaxBlackSquareLcci().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] findSquare(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] dp1 = new int[m][n];//以行为前缀和
            int[][] dp2 = new int[m][n];//以列为前缀和

            // 相减为0，说明这条边上面全是0，这是判断依据

            //枚举长度，枚举起点。
            return null;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
